24. 两两交换链表中的节点

分析

如何实现两两交换链表中的节点？
仔细思考我们会发现，这个操作实际上涉及到四个点

即，我们要交换 AB 两个节点，实际上涉及到前、A、B、后四个节点，其中需要修改的为前、A、B 三个节点的 next 指针。
而 AB 这两个节点其实也可以通过最前面那个节点的 next 指针访问到，于是思路就有了，用 while 循环，一次循环交换两个节点，交换完成后往后走两个节点，如果后面不足两个节点，就跳出来，这就是大概的思路。
在循环中设置下一次交换的头结点的时候，很容易搞错，因为节点的指针已经更换了，一个万无一失的办法就是从当前循环的 nowNode 通过 next 来访问 nowNode.next.next。

while 循环也可以换成递归调用，我们可以按照 206. 反转链表#递归三步分析法来解决这道题：

整个递归的终止条件，递归应该在什么时候结束？当当前元素之后不够凑成一对（2 个）的时候
本级递归应该做什么，在这一级递归中，应该完成什么任务？交换当前元素后面的两个元素，具体做法是更新 next 指针。此时我们会想到链表的头两个元素没有前面的节点了，他俩怎么交换呢？很简单，跟 203. 移除链表元素一样，加一个虚拟头节点即可。
找返回值，应该返回给上一级的返回值是什么？没有返回值，为什么，因为交换 A->B->C 种 AB 的位置，不影响链表的其他部分。所以可以不返回任何值给其他部分。

这个题跟 206. 反转链表的区别反转链表是从后往前反转，就是先反转后面的，再反转前面的，但是这个题，是先反转前面的，再反转后面的。反转链表的递归写法是需要返回值的，但是这道题的递归不需要

解题

public ListNode swapPairs(ListNode head) {
    ListNode dummyHead = new ListNode();
    dummyHead.next = head;
    ListNode nowNode = dummyHead;
    //两两一组,同时这一组的前一个节点为当前节点
    while (nowNode != null && nowNode.next != null && nowNode.next.next != null) {
        ListNode eleOne = nowNode.next;
        ListNode eleTwo = eleOne.next;
        // 交换之前，先把最终节点找到
        ListNode end = eleTwo.next;
        // 开始交换
        nowNode.next = eleTwo;
        eleTwo.next = eleOne;
        eleOne.next = end;
        //调整后,下一次循环的起点
        nowNode = eleOne;
        // 或者你也可以从最新的 nowNode 开始找
        // nowNode = nowNode.next.next;
    }
    return dummyHead.next;
}

不用 while，用递归也可以实现

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        revertAdjoinNode(dummyHead);
        return dummyHead.next;
    }

    public static void revertAdjoinNode(ListNode head){
        // 1. 确定最终的退出递归的条件
        if(head == null ||head.next == null||head.next.next == null ){
            return;
        }
        // 2. 当前循做的工作
        // 交换当前节点的后两个节点，再递归调用。
        ListNode nextNode = head.next;
        ListNode nextNextNode = head.next.next;
        // 可能为null
        ListNode nextNextNextNode = head.next.next.next;
        // 开始重新整理next指针
        head.next = nextNextNode;
        nextNextNode.next = nextNode;
        nextNode.next = nextNextNextNode;
        // 递归调用
        revertAdjoinNode(nextNode);
        // 3. 返回值
        // 不需要返回值
    }
}

更高级的方法：
用递归，递归的思路先交换后面的，再交换前面的，交换交换完后面的，
假设一开始是 A-B-C-D，最后一次交换，先交换 C 和 D，并最终返回 D，然后倒数第二次交换，直接设置 A 的下一个节点为 D，然后 B 的下一个节点是 A，最终返回 B，结果就是 B-A-D-C，
非常短小精妙，当然写起来也更容易写错。哈哈哈

public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    // 一开始就可以确定这一次递归要返回的元素，
    ListNode newHead = head.next;
    // 第一个元素的下一个元素为下一对要交换的元素的第二个元素，也就是下一对元素交换之后的排在前面的元素
    // 这一句是整个递归的精髓
    head.next = swapPairs(newHead.next);
    // 让这一对的第二个元素指向这一对的第一个元素
    newHead.next = head;
    // 返回这一对的第二个元素
    return newHead;
}

24. 两两交换链表中的节点

分析

解题

相关题